#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
const double PI=acos(-1.0);
const int MAXN=1e5+7;
struct Complex {
	double real,image;
	Complex(double a, double b) {
		real=a; image=b;
	}
	Complex() {
		real=0; image=0;
	}
	Complex operator + (const Complex& a) {
		return Complex(real+a.real, image+a.image);
	} 
	Complex operator - (const Complex& a) {
		return Complex(real-a.real, image-a.image);
	}
	Complex operator * (const Complex& a) {
		return Complex(real*a.real-image*a.image, real*a.image+image*a.real);
	}
};

Complex* RecursiveFFT(Complex a[], int n) {
	if (n==1)
		return a;
	Complex wn = Complex(cos(2*PI/n), sin(2*PI/n));
	Complex w = Complex(1, 0);
	
}
int main() {
	
	return 0;
}
